package com.ygu.HomeWork.NO02;

import com.ygu.charpter2_reverselist.level1.ReverseList;

public class helpEachOther {
    public static void main(String[] args) {
        int[] a = {1,2,3,4,5,6,7,8,9,10};
        ListNode nodeA = initLinkedList(a);
        System.out.println(toString(nodeA));
        ListNode result= null;
        int testMethod = 1;
        switch (testMethod) {
            case 1://1 使用for循环 和 递归
                result = reverseNode(nodeA);
                break;
            case 2://方法3：不适用虚拟结点的反转方法
                break;
            case 3:
                break;
        }

        System.out.println(toString(result));
    }

    private static ListNode reverseNode(ListNode head) {
        // 找到链表中间节点的前一个节点
        ListNode midPrev = findMidPrev(head);

        // 将链表分割为两个子链表
        ListNode secondHalfHead = midPrev.next;
        midPrev.next = null;

        //反转中点之后的
        secondHalfHead = ReverseListNode(secondHalfHead);
        System.out.println(toString(secondHalfHead));

        //得到两个新的链表进行合并
        // 合并两个链表
        ListNode mergedListHead = mergedList( head ,  secondHalfHead);
        return mergedListHead;
    }

    private static ListNode findMidPrev(ListNode head) {
        //找到中 进行反转中点之后的 然后进行插入
        ListNode slow = head;
        ListNode fast = head;

        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

    private static ListNode mergedList(ListNode list1, ListNode list2) {
        ListNode dummy = new ListNode(0);
        ListNode cur = dummy;

        while (list1 != null && list2 != null) {
            cur.next = list1;
            list1 = list1.next;
            cur = cur.next;

            cur.next = list2;
            list2 = list2.next;
            cur = cur.next;
        }

        if (list1 != null) {
            cur.next = list1;
        }
        return dummy.next;

    }

    private static ListNode ReverseListNode(ListNode head) {
        if(head == null || head.next == null) return head;

        ListNode last = ReverseListNode(head.next);
        head.next.next = head;
        head.next = null;
        return last;
    }

    /**
     * 初始化链表
     *
     * @param array
     * @return
     */
    private static ListNode initLinkedList(int[] array) {
        ListNode head = null, cur = null;

        for (int i = 0; i < array.length; i++) {
           ListNode newNode = new ListNode(array[i]);
            newNode.next = null;
            if (i == 0) {
                head = newNode;
                cur = head;
            } else {
                cur.next = newNode;
                cur = newNode;
            }
        }
        return head;
    }
    /**
     * 输出链表
     *
     * @param head 头节点
     */
    public static String toString(ListNode head) {
       ListNode current = head;
        StringBuilder sb = new StringBuilder();
        while (current != null) {
            sb.append(current.val).append("\t");
            current = current.next;
        }
        return sb.toString();
    }

}
